Current third generation (3G) and fourth generation (4G) 3rd Generation Partnership Project (3GPP) mobile networks typically use encryption as well as authentication in the control plane, whereas the user plane is protected by encryption only. WiMAX and Wireless Local Area Networks (WLAN)/WiFi networks on the other hand use authentication also for the user plane.
A known way of protecting user plane messaging is to use authentication tags which are generated by applying keyed cryptographic hash functions to messages, such as keyed-Hash Message Authentication Codes (HMAC) or Cipher Block Chaining Message Authentication Codes (CBC-MAC). A cryptographic hash function is a hash function that generates a cryptographic hash value, also known as message digest, for an arbitrary block of data, such as a message, such that any accidental or intentional change to the message, i.e., an error or modification, will change the hash value, at least with a certain high probability. Accordingly, the message digest can be used for providing integrity assurance on the message.
The problem with keyed cryptographic hash functions is that they are comparatively resource consuming, which hampers their use in constrained devices, i.e., devices with limited computing and battery resources such as Machine-to-Machine (M2M) and Internet-of-Things (IoT) types of devices. In addition, the increase in message length due to the message digest reduces the payload portion of the transmitted data and increases power consumption.
Some level of protection against random errors can be achieved by using Cyclic Redundancy Check (CRC) codes. CRC codes are a type of separable cyclic codes which are very resource-efficient and widely used in data communication and data storage for detecting burst errors. CRC processing can be efficiently implemented with Linear-Feedback Shift Registers (LFSRs). Common CRCs are (CRC-n means that a generator polynomial of degree n is used for encoding and decoding the CRC, where the degree is the largest coefficient of the CRC's generator polynomial):                CRC-16-CDMA2000: used in 3G mobile networks        CRC-CCITT: used in Bluetooth        CRC-32: used in Ethernet and High-Level Data Link Control (HDLC) protocols        CRC-40-GSM: used in GSM control channel.        
A CRC with a generator polynomial of degree n is able to detect all burst errors of length less than or equal to n and any error which is not a multiple of the generator polynomial.
While traditional CRC techniques are suitable for detecting random errors, they can easily be defeated by a malicious adversary. Since it is known to an adversary which generator polynomial is used by a certain CRC, he may easily craft a modified message which passes the CRC check at the receiver. This may, e.g., be achieved by adding to the original message an error which corresponds to a multiple of the generator polynomial.
A more resource efficient solution for providing data integrity in the user plane is to replace the conventional CRC by a cryptographically secure CRC, in the following also referred to as cryptographic CRC or cryptographic checksum. A cryptographic CRC has the same capability of detecting random errors as a traditional CRC, but is also capable of detecting, with high probability, any malicious error injected by an adversary.
A type of cryptographically secure CRC was proposed by Krawczyk [H. Krawczyk, “LFSR-based Hashing and Authentication”, in Advances in Cryptology—CRYPTO '94, Lecture Notes in Computer Science, Volume 839, Springer, 1994, pp. 129-139]. The proposed CRC requires an irreducible polynomial of degree n for generating the authentication tag, i.e., the CRC check bits. The basic idea is to let the CRC polynomial be a shared secret, known only to sender and receiver. This works satisfactorily from a security point of view, but still suffers from being resource inefficient since it is not trivial to find irreducible polynomials. Generating an irreducible polynomial, i.e., a polynomial which cannot be factored into the product of two or more non-trivial polynomials, requires either pseudo-randomly generating a polynomial and running a test for irreducibility, or pseudo-randomly selecting polynomials from a database of irreducible polynomials. The computational complexity of tests for irreducibility is of order n3 bit operations [see, e.g., S. Gao and D. Panario, “Tests and Constructions of Irreducible Polynomials over Finite Fields” in Foundations of Computational Mathematics, F. Cucker and M. Shub (Eds.), Springer, 1997, pp. 346-361], which is computationally demanding. Maintaining a database of irreducible polynomials is space consuming, since the number of irreducible polynomials for the most common CRC length, n=32, is 227=134.215.680, requiring 512 Mbytes of storage. In general, the number of irreducible degree-n polynomials over binary fields grows like 2n/n.